回溯法原理

回溯法也称试探法,它的基本思想是:从问题的某一种状态(初始状态)出发,搜索从这种状态出发所能达到的所有“状态”,当一条路走到“尽头”的时候(不能再前进),再后退一步或若干步,从另一种可能“状态”出发,继续搜索,直到所有的“路径”(状态)都试探过。这种不断“前进”、不断“回溯”寻找解的方法,就称作“回溯法”。

1.没回溯的匹配


/ab{1,3}c/ 匹配 abbbc

一次性到位,没有回溯

2.有回溯的匹配


  • 实例1

/ab{1,3}c/ 匹配 abbc

匹配第三个b的时候,文本为c,回退上一个状态,不再匹配B,而是匹配洗下一个正则符号C

  • 实例2

/".*"/ 匹配 "acd"ef

匹配过程: 匹配完第一个双引号,开始通配符匹配。 通配符匹配到f,然后发现没有第二个双引号。开始状态回退两步,发现可以匹配第二个双引号,然后结束。

怎么改?

answer

3.常见回溯形式


  • 贪婪量词

    b{1,3}

  • 惰性量词

    虽然惰性量词不贪,但也会有回溯的现象

    var string = "12345";
    var regex = /^(\d{1,3}?)(\d{1,3})$/;
    
  • 分支结构

    /can|candy/

    前面满足了,后面就不会实验了。

results matching ""

    No results matching ""